846C - Four Segments - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 5555;

ll n;
ll a[N];

int main(){
ios::sync_with_stdio(false);
cin.tie(0);

cin>>n;
for (int i=0; i<n; i++){
cin>>a[i];
}
ll cur=0,mx=0,l=0,r=0,m=0;
for (int i=0; i<n; i++){
cur+=a[i];
ll curr=0;
if (mx<cur){
l=m=r=i+1;
mx=cur;
}
int L=0;
for (int j=0; j<=i; j++){
curr+=a[j];
if (curr>0){
curr=0;
L=j+1;
}
if (mx<cur-curr){
l=L,m=j+1,r=i+1;
mx=cur-curr;
}
}
}
cout<<l<<" "<<m<<" "<<r<<endl;
return 0;
}